Symbolic Complexity for Nucleotide Sequences: A Sign of the Genome Structure

摘要

We introduce a method to estimate the complexity function of symbolicdynamical systems from a finite sequence of symbols. We test such complexityestimator on several symbolic dynamical systems whose complexity functions areknown exactly. We use this technique to estimate the complexity function forgenomes of several organisms under the assumption that a genome is a sequenceproduced by a (unknown) dynamical system. We show that the genome of severalorganisms share the property that their complexity functions behavesexponentially for words of small length $\ell$ ($0\leq \ell \leq 10$) andlinearly for word lengths in the range $11 \leq \ell \leq 50$. It is also foundthat the species which are phylogenetically close each other have similarcomplexity functions calculated from a sample of their corresponding codingregions.